package 并查集;

import com.alibaba.fastjson.JSON;

import java.util.ArrayDeque;
import java.util.Deque;

public class No130被围绕的区域 {

    /**
     * 给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
     * 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
     *
     * 示例:
     * X X X X
     * X O O X
     * X X O X
     * X O X X
     * 运行你的函数后，矩阵变为：
     * X X X X
     * X X X X
     * X X X X
     * X O X X
     */

    public void solve(char[][] board) {
        /**
         * 并查集的解法:
         * 虚拟一个O地面,让所有O地面融合成一块
         * 靠边的O地面向内延申即可,最后非虚拟地面直接置为X
         */
        if(board.length==0)
            return;
        int allLength=board.length;
        int itemLength=board[0].length;
        int size=allLength*itemLength;
        int[][] around={{-1,0},{0,1},{1,0},{0,-1}};
        //多出一个虚拟的O地面
        UnionFind unionFind=new UnionFind(size+1);

        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                if((i==0||i==allLength-1||j==0||j==itemLength-1)&&board[i][j]=='O'){
                    //直接融合外边的O地面
                    unionFind.union(itemLength*i+j,size);
                    Deque<Integer> queue=new ArrayDeque<>();
                    //这条公式是对的,itemLength为3,那么最大的startY是2!不是3
                    queue.addLast(i*itemLength+j);
                    while (!queue.isEmpty()){
                        Integer removeFirst = queue.removeFirst();
                        for (int k = 0; k < 4; k++) {
                            int newX=removeFirst/itemLength+around[k][0];
                            int newY=removeFirst%itemLength+around[k][1];
                            /**
                             * 外边的O地面向内延申
                             */
                            if(newX>=0&&newX<=allLength-1&&newY>=0&&newY<=itemLength-1
                                    &&board[newX][newY]=='O'&&unionFind.find(newX*itemLength+newY)!=unionFind.find(size)) {
                                queue.addLast(newX * itemLength + newY);
                                unionFind.union(itemLength * newX + newY, size);
                            }
                        }
                    }
                }
            }
        }

        int dump = unionFind.find(size);
        for (int i = 0; i < size; i++) {
            if(unionFind.find(i)!=dump){
                board[i/itemLength][i%itemLength]='X';
            }
        }

    }

    @SuppressWarnings("all")
    public static void main(String[] args) {
        char[][] arr=
                {{'X','O','O','X','X','X','O','X','O','O'},
                        {'X','O','X','X','X','X','X','X','X','X'},
                        {'X','X','X','X','O','X','X','X','X','X'},
                        {'X','O','X','X','X','O','X','X','X','O'},
                        {'O','X','X','X','O','X','O','X','O','X'},
                        {'X','X','O','X','X','O','O','X','X','X'},
                        {'O','X','X','O','O','X','O','X','X','O'},
                        {'O','X','X','X','X','X','O','X','X','X'},
                        {'X','O','O','X','X','O','X','X','O','O'},
                        {'X','X','X','O','O','X','O','X','X','O'}};
        No130被围绕的区域 n=new No130被围绕的区域();
        n.solve(arr);
        System.out.println(JSON.toJSONString(arr));
    }

}
